package algo;

/**
 *
 * @author <a href="mailto:christian.dramsy@gmail.com>DRAMSY Christian</a>
 */
public class UtilitaireTas {

    /**
     * retourne l'indice de père de i;
     * @param i
     * @return 
     */
    private static int getIndicePere(int i) {
        //   si i est pair
        int retour = (int) ((i + 1) / 2) - 1;
        return (retour < 0 ? 0 : retour);
    }

    /**
     * Retourne l'indice du fils gauche de i
     * @param i
     * @return 
     */
    private static int getIndiceFilsGauche(int i) {
        return ((i + 1) * 2 - 1);
    }

    /**
     * Retourne l'indice du fils droit de i
     * @param i
     * @return 
     */
    private static int getIndiceFilsDroit(int i) {
        return ((i + 1) * 2);
    }

    /**
     * Ajoute un noeud dans un tas 
     * Pour cet algorithme, on peut éfféctuer h echanges au maximum. h etait la hauteur de l'arbre
     * @param tas
     * @param v
     * @return le nouveau tas
     */
    public static int[] ajouter(int[] tas, int v) {
        /**
         * A savoir : 
         *  -   Pour tout i de 2 à n(nombre de noeud de l'arbre)
         *      -   père de Tas[i] est Tas[partieEntiere(i/2)]
         *  -   Pour tout i de 1 à partieEntière(n/2)
         *      -   fils gauche de Tas[i] est Tas[2i]
         *      -   fils droit de Tas[i] est Tas[2i+1]
         */
        int[] newTas = new int[tas.length + 1];
        //  si l'arbre etait vide
        if (tas.length == 0) {
            newTas[0] = v;
        } else {
            //  Copie de tas dans newTas
            System.arraycopy(tas, 0, newTas, 0, tas.length);

            //  placement de v sur la dernière feuille libre de l'arbre(dernière case du tableau)
            int indiceV = tas.length;
            newTas[indiceV] = v;
            //  récuperation du père de v
            int indicePereV = UtilitaireTas.getIndicePere(indiceV);
            int pereV = newTas[indicePereV];

            while (v <= pereV) {
                //System.out.println(indicePereV + ":" + indiceV);
                if (indicePereV != indiceV) {

                    //  Echange de v et pereV dans l'arbre
                    //  -   Echange de valeur
                    int tmp = newTas[indiceV];
                    newTas[indiceV] = newTas[indicePereV];
                    newTas[indicePereV] = tmp;
                    //  -   Echange d'indice
                    indiceV = indicePereV;

                    indicePereV = UtilitaireTas.getIndicePere(indiceV);
                    pereV = newTas[indicePereV];
                } else {
                    break;
                }
            }
        }
        return newTas;
    }

    /**
     * Retourne la valeur de la racine de l'arbre(représenté par le tas) et supprime la racine de l'abre
     * @param Tas
     * @return 
     */
    public static int suppressionRacine(int[] Tas) {
        if (Tas.length > 0) {
            int valeurRetour = Tas[0];
            int indiceRacine = 0;
            int indiceMinimum;
            int indiceFilsGauche;
            int indiceFilsDroit;

            //  Le nouveau tas sera un tas avec une valeure en moin, donc la taille diminue
            int[] newTas = new int[Tas.length - 1];

            //  copie de tas dans newTas(ATTENTION : la valeur de la dernière feuille es perdue)
            System.arraycopy(Tas, 0, newTas, 0, Tas.length - 1);
            //  Remplacement de la valeur de la racine par la valeur de la dernière feuille du tas de depart
            newTas[indiceRacine] = Tas[Tas.length - 1];

            indiceFilsDroit = UtilitaireTas.getIndiceFilsDroit(indiceRacine);
            indiceFilsGauche = UtilitaireTas.getIndiceFilsGauche(indiceRacine);
            indiceMinimum = newTas[indiceFilsDroit] > newTas[indiceFilsGauche] ? indiceFilsGauche : indiceFilsDroit;


            while (newTas[indiceRacine] > newTas[indiceMinimum]) {
                UtilitaireAffichage.afficher(newTas);
                int tmp = newTas[indiceRacine];
                newTas[indiceRacine] = newTas[indiceMinimum];
                newTas[indiceMinimum] = tmp;

                indiceRacine = indiceMinimum;

                indiceFilsDroit = UtilitaireTas.getIndiceFilsDroit(indiceRacine);
                indiceFilsGauche = UtilitaireTas.getIndiceFilsGauche(indiceRacine);

                //  la racine est une feuille
                if (indiceFilsGauche >= newTas.length) {
                    break;
                }
                //  S'il n'a pas de fils droit(Donc il n'a qu'un fils gauche)
                if (indiceFilsDroit >= newTas.length) {
                    indiceMinimum = indiceFilsGauche;
                } else {
                    indiceMinimum = newTas[indiceFilsDroit] > newTas[indiceFilsGauche] ? indiceFilsGauche : indiceFilsDroit;
                }
            }
            System.out.print("LE NOUVEAU TAS\n");
            UtilitaireAffichage.afficher(newTas);

            return valeurRetour;
        }
        //  S'il n'y a pas de valeur dans le tas on retourne juste moin_infini
        return Integer.MIN_VALUE;
    }
}
